package LeedCode_BinaryTree;

/**
 * Created with IntelliJ IDEA.
 * Description:判断是否是平衡二叉树
 * User: 阿宾
 * Date: 2024-11-21
 * Time: 09:54
 */
public class Demo4 {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }
    public int getHeight(TreeNode root){
        if(root == null){
            return 0;
        }
        int LD = getHeight(root.left);
        int RD = getHeight(root.right);
        return LD > RD ? LD+1 : RD+1;
    }
    //可以遍历每个节点，然后计算每个节点的高度，如果相差大于1，则不是平衡二叉树
    public boolean isBalanced1(TreeNode root) {
        //空树也是平衡二叉树
        if(root == null){
            return true;
        }
        int left = getHeight(root.left);
        int right = getHeight(root.right);

        return Math.abs(left-right) <= 1 && isBalanced1(root.left) && isBalanced1(root.right);
    }

    //上述方法是第一种，时间复杂度较高O(n^2)
    //-------------------------------------------------------------
    //此时时间复杂度是O(n)
    //返回值为-1表示不是平衡二叉树
    public int checkHeight(TreeNode root){
        //空树的高度为1
        if(root == null){
            return 0;
        }
        int leftHeight = checkHeight(root.left);
        //检查左子树是否平衡
        if(leftHeight == -1){
            return -1;
        }
        int rightHeight = checkHeight(root.right);
        //检查右子树是否平衡
        if(rightHeight == -1){
            return -1;
        }
        //检查左右子树高度差是否满足平衡二叉树要求
        if(Math.abs(leftHeight-rightHeight)>1){
            return -1;
        }
        //最后返回结点高度，即左右高度最大值+1
        return (Math.max(leftHeight, rightHeight)) + 1;
    }
    public boolean isBalanced(TreeNode root) {
        /*if(cheackHeight(root) == -1){
            return false;
        }
        return true;*/
        return checkHeight(root) != -1;
    }
    public static void main(String[] args) {

    }
}
